package com.xy6.struct.tree;

import static org.junit.Assert.assertEquals;

import java.util.List;

import org.junit.Test;

/**
 * 二叉树测试用例
 * 
 * @author zhang
 * @since 2017-09-17
 */
public class BinaryTreeTest {

	/**
	 * 测试多叉树遍历顺序
	 */
	@Test
	public void testPrint1() {
		BinaryTree<String> tree = makeTree();

		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("1");
		tree.setRoot(root);

		BinaryTreeNode<String> node2 = new BinaryTreeNode<String>("2");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node5 = new BinaryTreeNode<String>("5");
		BinaryTreeNode<String> node6 = new BinaryTreeNode<String>("6");
		BinaryTreeNode<String> node7 = new BinaryTreeNode<String>("7");

		root.setLeft(node2);
		root.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setRight(node6);
		node6.setRight(node7);
		
		return tree;
	}

	/**
	 * 输出每个节点信息
	 */
	private void print(List<BinaryTreeNode<String>> nodes) {
		if (nodes == null || nodes.size() == 0) {
			System.out.println("empty tree");
			return;
		}
		for (BinaryTreeNode<String> elem : nodes) {
			System.out.println(String.format("parent: %s, node: %s, left: %s, right: %s",
					null == elem.getParent() ? null : elem.getParent().getData(), elem.getData(), null == elem
							.getLeft() ? null : elem.getLeft().getData(), null == elem.getRight() ? null : elem
							.getRight().getData()));
		}
		System.out.println("#############");
	}
	
	@Test
	public void testSearch1(){
		BinaryTree<String> tree = makeTree();
		BinaryTreeNode<String> node = tree.search("1");
		assertEquals(true, "1".equals(node.getData()));
	}
	
	@Test
	public void testSearch2(){
		BinaryTree<String> tree = makeTree();
		BinaryTreeNode<String> node = tree.search("5");
		assertEquals(true, "5".equals(node.getData()));
	}
	
	@Test
	public void testSearchNull1(){
		BinaryTree<String> tree = makeTree();
		BinaryTreeNode<String> node = tree.search("50");
		assertEquals(true, null == node);
	}
	
	@Test
	public void testAdd1(){
		BinaryTree<String> tree = makeTree();
		BinaryTreeNode<String> node = tree.search("5");
		BinaryTreeNode<String> node8 = new BinaryTreeNode<>("8");
		BinaryTreeNode<String> node9 = new BinaryTreeNode<>("9");
		node.setLeft(node8);
		node8.setRight(node9);
		
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveLeaf1(){
		BinaryTree<String> tree = makeTree();
		BinaryTreeNode<String> node7 = tree.search("7");
		tree.remove(node7);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemove2(){
		BinaryTree<String> tree = makeTree();
		print(tree.getNodes());
		BinaryTreeNode<String> node3 = tree.search("3");
		tree.remove(node3);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemove3(){
		BinaryTree<String> tree = makeTree();
		print(tree.getNodes());
		BinaryTreeNode<String> node2 = tree.search("2");
		tree.remove(node2);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot4(){
		BinaryTree<String> tree = makeTree();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree2(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("0");
		tree.setRoot(root);

		BinaryTreeNode<String> node1 = new BinaryTreeNode<String>("1");
		BinaryTreeNode<String> node2 = new BinaryTreeNode<String>("2");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node5 = new BinaryTreeNode<String>("5");
		BinaryTreeNode<String> node6 = new BinaryTreeNode<String>("6");

		root.setLeft(node1);
		root.setRight(node2);
		node1.setLeft(node3);
		node1.setRight(node4);
		node2.setRight(node5);
		node5.setRight(node6);
		
		return tree;
	}
	
	@Test
	public void testRemove21(){
		BinaryTree<String> tree = makeTree2();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot22(){
		BinaryTree<String> tree = makeTree2();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	@Test
	public void testRemove23(){
		BinaryTree<String> tree = makeTree2();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("2");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree3(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("0");
		tree.setRoot(root);

		BinaryTreeNode<String> node1 = new BinaryTreeNode<String>("1");
		BinaryTreeNode<String> node2 = new BinaryTreeNode<String>("2");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node5 = new BinaryTreeNode<String>("5");
		BinaryTreeNode<String> node6 = new BinaryTreeNode<String>("6");
		BinaryTreeNode<String> node7 = new BinaryTreeNode<String>("7");
		BinaryTreeNode<String> node8 = new BinaryTreeNode<String>("8");

		root.setLeft(node1);
		root.setRight(node2);
		node1.setLeft(node3);
		node1.setRight(node4);
		node3.setLeft(node7);
		node3.setRight(node8);
		node2.setRight(node5);
		node5.setRight(node6);
		
		return tree;
	}
	
	@Test
	public void testRemove31(){
		BinaryTree<String> tree = makeTree3();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot32(){
		BinaryTree<String> tree = makeTree3();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree4(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("0");
		tree.setRoot(root);

		BinaryTreeNode<String> node1 = new BinaryTreeNode<String>("1");
		BinaryTreeNode<String> node2 = new BinaryTreeNode<String>("2");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node5 = new BinaryTreeNode<String>("5");
		BinaryTreeNode<String> node6 = new BinaryTreeNode<String>("6");
		BinaryTreeNode<String> node8 = new BinaryTreeNode<String>("8");

		root.setLeft(node1);
		root.setRight(node2);
		node1.setLeft(node3);
		node1.setRight(node4);
		node3.setRight(node8);
		node2.setRight(node5);
		node5.setRight(node6);
		
		return tree;
	}
	
	@Test
	public void testRemove41(){
		BinaryTree<String> tree = makeTree4();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot42(){
		BinaryTree<String> tree = makeTree4();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree5(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("0");
		tree.setRoot(root);

		BinaryTreeNode<String> node1 = new BinaryTreeNode<String>("1");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node7 = new BinaryTreeNode<String>("7");
		BinaryTreeNode<String> node8 = new BinaryTreeNode<String>("8");
		BinaryTreeNode<String> node9 = new BinaryTreeNode<String>("9");
		BinaryTreeNode<String> node10 = new BinaryTreeNode<String>("10");

		root.setLeft(node1);
		node1.setLeft(node3);
		node1.setRight(node4);
		node3.setLeft(node7);
		node3.setRight(node8);
		node7.setLeft(node10);
		node7.setRight(node9);
		
		return tree;
	}
	
	@Test
	public void testRemove51(){
		BinaryTree<String> tree = makeTree5();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot52(){
		BinaryTree<String> tree = makeTree5();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree6(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("0");
		tree.setRoot(root);

		BinaryTreeNode<String> node1 = new BinaryTreeNode<String>("1");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node8 = new BinaryTreeNode<String>("8");
		BinaryTreeNode<String> node9 = new BinaryTreeNode<String>("9");
		BinaryTreeNode<String> node10 = new BinaryTreeNode<String>("10");

		root.setLeft(node1);
		node1.setLeft(node3);
		node1.setRight(node4);
		node3.setRight(node8);
		node8.setLeft(node10);
		node8.setRight(node9);
		
		return tree;
	}
	
	@Test
	public void testRemove61(){
		BinaryTree<String> tree = makeTree6();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot62(){
		BinaryTree<String> tree = makeTree6();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	private BinaryTree<String> makeTree7(){
		BinaryTree<String> tree = new BinaryTree<String>();
		BinaryTreeNode<String> root = new BinaryTreeNode<String>("0");
		tree.setRoot(root);

		BinaryTreeNode<String> node1 = new BinaryTreeNode<String>("1");
		BinaryTreeNode<String> node3 = new BinaryTreeNode<String>("3");
		BinaryTreeNode<String> node4 = new BinaryTreeNode<String>("4");
		BinaryTreeNode<String> node7 = new BinaryTreeNode<String>("7");
		BinaryTreeNode<String> node8 = new BinaryTreeNode<String>("8");
		BinaryTreeNode<String> node9 = new BinaryTreeNode<String>("9");
		BinaryTreeNode<String> node10 = new BinaryTreeNode<String>("10");

		root.setLeft(node1);
		node1.setLeft(node3);
		node1.setRight(node4);
		node3.setLeft(node7);
		node3.setRight(node8);
		node7.setRight(node9);
		node9.setRight(node10);
		
		return tree;
	}
	
	@Test
	public void testRemove71(){
		BinaryTree<String> tree = makeTree7();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.remove(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoveRoot72(){
		BinaryTree<String> tree = makeTree7();
		print(tree.getNodes());
		tree.remove(tree.getRoot());
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoceCascade71(){
		BinaryTree<String> tree = makeTree7();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("1");
		tree.removeCascade(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoceCascade72(){
		BinaryTree<String> tree = makeTree7();
		print(tree.getNodes());
		tree.removeCascade(tree.getRoot());
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoceCascade11(){
		BinaryTree<String> tree = makeTree();
		print(tree.getNodes());
		BinaryTreeNode<String> node = tree.search("2");
		tree.removeCascade(node);
		print(tree.getNodes());
	}
	
	@Test
	public void testRemoceCascade12(){
		BinaryTree<String> tree = makeTree();
		print(tree.getNodes());
		tree.removeCascade(tree.getRoot());
		print(tree.getNodes());
	}
	
}
